package com.cat.bitOperation;

import java.util.*;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/split-and-merge-array-transformation/
 * @create 2025/11/1 17:08
 * @since JDK17
 */

public class Solution14 {
    public int minSplitMerge(int[] nums1, int[] nums2) {
        List<Integer> list2 = Arrays.stream(nums2).boxed().toList(), list1 = Arrays.stream(nums1).boxed().toList();
        Set<List<Integer>> set = new HashSet<>();   // 去重
        List<List<Integer>> q = new ArrayList<>();  // 记录所有的状态
        q.add(list1);
        set.add(list1);
        for (int i = 0; ; i++) {
            var t = new ArrayList<>(q); // 复制一份出来
            q = new ArrayList<>();
            for (int j = 0; j < t.size(); j++) {
                var a = t.get(j);
                if (a.equals(list2)) {  // 找到完全一样的了
                    return i;
                }
                // 开始枚举所有的状态
                for (int l = 0; l < a.size(); l++) {
                    for (int r = l + 1; r <= a.size(); r++) {
                        // 所有的区间
                        List<Integer> sub = a.subList(l, r);
                        List<Integer> b = new ArrayList<>(a);
                        b.subList(l, r).clear();    // 在b数组中清楚[l,r)
                        for (int k = 0; k < b.size(); k++) {
                            // 枚举所有的插入点
                            var c = new ArrayList<>(b);
                            c.addAll(k, sub);
                            if (set.add(c)) {
                                q.add(c);
                            }
                        }
                    }
                }
            }


        }
    }
}
